<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en" dir="ltr"> 
<head> 
<title>Parsing - Wikipedia, the free encyclopedia</title> 
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 
<meta http-equiv="Content-Style-Type" content="text/css" /> 
<meta name="generator" content="MediaWiki 1.16alpha-wmf" /> 
<link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Parsing&amp;action=edit" /> 
<link rel="edit" title="Edit this page" href="/w/index.php?title=Parsing&amp;action=edit" /> 
<link rel="stylesheet" type="text/css" href="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/css/combined.min.css?16" /> 
<link rel="stylesheet" type="text/css" href="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/css/vector/jquery-ui-1.7.2.css?1.7.2" /> 
<link rel="apple-touch-icon" href="http://en.wikipedia.org/apple-touch-icon.png" /> 
<link rel="shortcut icon" href="/favicon.ico" /> 
<link rel="search" type="application/opensearchdescription+xml" href="/w/opensearch_desc.php" title="Wikipedia (en)" /> 
<link rel="copyright" href="http://creativecommons.org/licenses/by-sa/3.0/" /> 
<link rel="alternate" type="application/rss+xml" title="Wikipedia RSS Feed" href="/w/index.php?title=Special:RecentChanges&amp;feed=rss" /> 
<link rel="alternate" type="application/atom+xml" title="Wikipedia Atom Feed" href="/w/index.php?title=Special:RecentChanges&amp;feed=atom" /> 
<link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/common/shared.css?257z2" type="text/css" media="screen" /> 
<link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/common/commonPrint.css?257z2" type="text/css" media="print" /> 
<link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/monobook/main.css?257z2" type="text/css" media="screen" /> 
<link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/chick/main.css?257z2" type="text/css" media="handheld" /> 
<!--[if lt IE 5.5000]><link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/monobook/IE50Fixes.css?257z2" type="text/css" media="screen" /><![endif]--> 
<!--[if IE 5.5000]><link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/monobook/IE55Fixes.css?257z2" type="text/css" media="screen" /><![endif]--> 
<!--[if IE 6]><link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/monobook/IE60Fixes.css?257z2" type="text/css" media="screen" /><![endif]--> 
<!--[if IE 7]><link rel="stylesheet" href="http://bits.wikimedia.org/skins-1.5/monobook/IE70Fixes.css?257z2" type="text/css" media="screen" /><![endif]--> 
<link rel="stylesheet" href="/w/index.php?title=MediaWiki:Common.css&amp;usemsgcache=yes&amp;ctype=text%2Fcss&amp;smaxage=2678400&amp;action=raw&amp;maxage=2678400" type="text/css" media="all" /> 
<link rel="stylesheet" href="/w/index.php?title=MediaWiki:Print.css&amp;usemsgcache=yes&amp;ctype=text%2Fcss&amp;smaxage=2678400&amp;action=raw&amp;maxage=2678400" type="text/css" media="print" /> 
<link rel="stylesheet" href="/w/index.php?title=MediaWiki:Handheld.css&amp;usemsgcache=yes&amp;ctype=text%2Fcss&amp;smaxage=2678400&amp;action=raw&amp;maxage=2678400" type="text/css" media="handheld" /> 
<link rel="stylesheet" href="/w/index.php?title=MediaWiki:Monobook.css&amp;usemsgcache=yes&amp;ctype=text%2Fcss&amp;smaxage=2678400&amp;action=raw&amp;maxage=2678400" type="text/css" media="all" /> 
<link rel="stylesheet" href="/w/index.php?title=-&amp;action=raw&amp;maxage=2678400&amp;gen=css" type="text/css" media="all" /> 
<script type="text/javascript"> 
var skin="monobook",
stylepath="http://bits.wikimedia.org/skins-1.5",
wgArticlePath="/wiki/$1",
wgScriptPath="/w",
wgScriptExtension=".php",
wgScript="/w/index.php",
wgVariantArticlePath=false,
wgActionPaths={},
wgServer="http://en.wikipedia.org",
wgCanonicalNamespace="",
wgCanonicalSpecialPageName=false,
wgNamespaceNumber=0,
wgPageName="Parsing",
wgTitle="Parsing",
wgAction="view",
wgArticleId=310015,
wgIsArticle=true,
wgUserName=null,
wgUserGroups=null,
wgUserLanguage="en",
wgContentLanguage="en",
wgBreakFrames=false,
wgCurRevisionId=333278307,
wgVersion="1.16alpha-wmf",
wgEnableAPI=true,
wgEnableWriteAPI=true,
wgSeparatorTransformTable=["", ""],
wgDigitTransformTable=["", ""],
wgMainPageTitle="Main Page",
wgFormattedNamespaces={"-2": "Media", "-1": "Special", "0": "", "1": "Talk", "2": "User", "3": "User talk", "4": "Wikipedia", "5": "Wikipedia talk", "6": "File", "7": "File talk", "8": "MediaWiki", "9": "MediaWiki talk", "10": "Template", "11": "Template talk", "12": "Help", "13": "Help talk", "14": "Category", "15": "Category talk", "100": "Portal", "101": "Portal talk", "108": "Book", "109": "Book talk"},
wgNamespaceIds={"media": -2, "special": -1, "": 0, "talk": 1, "user": 2, "user_talk": 3, "wikipedia": 4, "wikipedia_talk": 5, "file": 6, "file_talk": 7, "mediawiki": 8, "mediawiki_talk": 9, "template": 10, "template_talk": 11, "help": 12, "help_talk": 13, "category": 14, "category_talk": 15, "portal": 100, "portal_talk": 101, "book": 108, "book_talk": 109, "wp": 4, "wt": 5, "image": 6, "image_talk": 7},
wgMWSuggestTemplate="http://en.wikipedia.org/w/api.php?action=opensearch\x26search={searchTerms}\x26namespace={namespaces}\x26suggest",
wgDBname="enwiki",
wgSearchNamespaces=[0],
wgMWSuggestMessages=["with suggestions", "no suggestions"],
wgRestrictionEdit=[],
wgRestrictionMove=[],
wgTrackingToken="91e9bdf024c9329142a212ed0634906b",
wgClickTrackingIsThrottled=true,
wgNotice="",
wgNoticeLocal="";
</script> 
<script src="http://bits.wikimedia.org/skins-1.5/common/wikibits.js?urid=257z2_1254880607" type="text/javascript"></script> 
<script src="http://bits.wikimedia.org/skins-1.5/common/ajax.js?urid=257z2" type="text/javascript"></script> 
<script src="http://bits.wikimedia.org/skins-1.5/common/mwsuggest.js?urid=257z2" type="text/javascript"></script> 
<script type="text/javascript" src="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/js/js2.combined.min.js?8"></script> 
<script type="text/javascript" src="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/js/plugins.combined.min.js?68"></script> 
<script type="text/javascript" src="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/CollapsibleTabs/CollapsibleTabs.js?9"></script> 
<script type="text/javascript" src="http://bits.wikimedia.org/w/extensions/UsabilityInitiative/ClickTracking/ClickTracking.js?4"></script> 
<script type="text/javascript" src="http://upload.wikimedia.org/centralnotice/wikipedia/en/centralnotice.js?257z2"></script> 
 
<!--[if lt IE 7]><script type="text/javascript" src="http://bits.wikimedia.org/skins-1.5/common/IEFixes.js?257z2"></script>
    <meta http-equiv="imagetoolbar" content="no" /><![endif]--> 
<script src="/w/index.php?title=-&amp;action=raw&amp;gen=js&amp;useskin=monobook&amp;urid=257z2_336800052" type="text/javascript"></script> 
 
</head> 
<body class="mediawiki ltr ns-0 ns-subject page-Parsing skin-monobook"> 
    <div id="globalWrapper"> 
        <div id="column-content"> 
    <div id="content"> 
        <a id="top"></a> 
        <div id="siteNotice"><script type='text/javascript'>if (wgNotice != '') document.writeln(wgNotice);</script></div>      <h1 id="firstHeading" class="firstHeading">Parsing</h1> 
        <div id="bodyContent"> 
            <h3 id="siteSub">From Wikipedia, the free encyclopedia</h3> 
            <div id="contentSub"></div> 
                                    <div id="jump-to-nav">Jump to: <a href="#column-one">navigation</a>, <a href="#searchInput">search</a></div>            <!-- start content --> 
            <div class="dablink"><span class="plainlinks selfreference">For help with Wikipedia's parser functions, see <a href="http://www.mediawiki.org/wiki/Help:Extension:ParserFunctions" class="extiw" title="mw:Help:Extension:ParserFunctions">mw:Help:Extension:ParserFunctions</a>.</span></div> 
<div class="dablink">"Parser" redirects here. For the computer programming language, see <a href="/wiki/Parser_(CGI_language)" title="Parser (CGI language)">Parser (CGI language)</a>.</div> 
<table class="metadata plainlinks ambox ambox-content" style=""> 
<tr> 
<td class="mbox-image"> 
<div style="width: 52px;"><a href="/wiki/File:Question_book-new.svg" class="image"><img alt="Question book-new.svg" src="http://upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" width="50" height="39" /></a></div> 
</td> 
<td class="mbox-text" style="">This article <b>needs additional <a href="/wiki/Wikipedia:Citing_sources#Inline_citations" title="Wikipedia:Citing sources">citations</a> for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a>.</b><br /> 
<small>Please help <a href="http://en.wikipedia.org/w/index.php?title=Parsing&amp;action=edit" class="external text" rel="nofollow">improve this article</a> by adding <a href="/wiki/Wikipedia:Reliable_sources" title="Wikipedia:Reliable sources">reliable references</a>. Unsourced material may be <a href="/wiki/Template:Fact" title="Template:Fact" class="mw-redirect">challenged</a> and <a href="/wiki/Wikipedia:Verifiability#Burden_of_evidence" title="Wikipedia:Verifiability">removed</a>. <small><i>(August 2008)</i></small></small></td> 
</tr> 
</table> 
<table class="metadata plainlinks mbox-small" style="border:1px solid #aaa; background-color:#f9f9f9;"> 
<tr> 
<td class="mbox-image"><a href="http://en.wiktionary.org/wiki/Special:Search/Parsing" title="Search Wiktionary"><img alt="Search Wiktionary" src="http://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Wiktionary-logo-en.svg/37px-Wiktionary-logo-en.svg.png" width="37" height="40" /></a></td> 
<td class="mbox-text" style="">Look up <i><b><a href="http://en.wiktionary.org/wiki/Special:Search/parsing" class="extiw" title="wiktionary:Special:Search/parsing">parsing</a></b></i> in <a href="/wiki/Wiktionary" title="Wiktionary">Wiktionary</a>, the free dictionary.</td> 
</tr> 
</table> 
<p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a> and <a href="/wiki/Linguistics" title="Linguistics">linguistics</a>, <b>parsing</b>, or, more formally, <b>syntactic analysis</b>, is the process of analyzing a text, made of a sequence of <a href="/wiki/Lexical_analysis#Token" title="Lexical analysis">tokens</a> (for example, words), to determine its grammatical structure with respect to a given (more or less) <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a>.</p> 
<p>Parsing is also an earlier term for the diagramming of sentences of <a href="/wiki/Natural_languages" title="Natural languages" class="mw-redirect">natural languages</a>, and is still used for the diagramming of <a href="/wiki/Inflection" title="Inflection">inflected</a> languages, such as the <a href="/wiki/Romance_languages" title="Romance languages">Romance languages</a> or <a href="/wiki/Latin" title="Latin">Latin</a>. The term parsing comes from Latin <i>pars</i> (<i>ōrātiōnis</i>), meaning <a href="/wiki/Part_of_speech" title="Part of speech" class="mw-redirect">part (of speech)</a>.<sup id="cite_ref-0" class="reference"><a href="#cite_note-0"><span>[</span>1<span>]</span></a></sup><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span>[</span>2<span>]</span></a></sup></p> 
<table id="toc" class="toc"> 
<tr> 
<td> 
<div id="toctitle"> 
<h2>Contents</h2> 
</div> 
<ul> 
<li class="toclevel-1 tocsection-1"><a href="#Parser"><span class="tocnumber">1</span> <span class="toctext">Parser</span></a></li> 
<li class="toclevel-1 tocsection-2"><a href="#Human_languages"><span class="tocnumber">2</span> <span class="toctext">Human languages</span></a></li> 
<li class="toclevel-1 tocsection-3"><a href="#Programming_languages"><span class="tocnumber">3</span> <span class="toctext">Programming languages</span></a> 
<ul> 
<li class="toclevel-2 tocsection-4"><a href="#Overview_of_process"><span class="tocnumber">3.1</span> <span class="toctext">Overview of process</span></a></li> 
</ul> 
</li> 
<li class="toclevel-1 tocsection-5"><a href="#Types_of_parser"><span class="tocnumber">4</span> <span class="toctext">Types of parser</span></a></li> 
<li class="toclevel-1 tocsection-6"><a href="#Examples_of_parsers"><span class="tocnumber">5</span> <span class="toctext">Examples of parsers</span></a> 
<ul> 
<li class="toclevel-2 tocsection-7"><a href="#Top-down_parsers"><span class="tocnumber">5.1</span> <span class="toctext">Top-down parsers</span></a></li> 
<li class="toclevel-2 tocsection-8"><a href="#Bottom-up_parsers"><span class="tocnumber">5.2</span> <span class="toctext">Bottom-up parsers</span></a></li> 
<li class="toclevel-2 tocsection-9"><a href="#Parser_development_software"><span class="tocnumber">5.3</span> <span class="toctext">Parser development software</span></a></li> 
</ul> 
</li> 
<li class="toclevel-1 tocsection-10"><a href="#See_also"><span class="tocnumber">6</span> <span class="toctext">See also</span></a></li> 
<li class="toclevel-1 tocsection-11"><a href="#References"><span class="tocnumber">7</span> <span class="toctext">References</span></a></li> 
<li class="toclevel-1 tocsection-12"><a href="#Further_reading"><span class="tocnumber">8</span> <span class="toctext">Further reading</span></a></li> 
<li class="toclevel-1 tocsection-13"><a href="#External_links"><span class="tocnumber">9</span> <span class="toctext">External links</span></a></li> 
</ul> 
</td> 
</tr> 
</table> 
<script type="text/javascript"> 
//<![CDATA[
if (window.showTocToggle) { var tocShowText = "show"; var tocHideText = "hide"; showTocToggle(); } 
//]]>
</script> 
<h2><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=1" title="Edit section: Parser">edit</a>]</span> <span class="mw-headline" id="Parser">Parser</span></h2> 
<p>In computing, a <b>parser</b> is one of the components in an <a href="/wiki/Interpreter_(computing)" title="Interpreter (computing)">interpreter</a> or <a href="/wiki/Compiler" title="Compiler">compiler</a>, which checks for correct syntax and builds a <a href="/wiki/Data_structure" title="Data structure">data structure</a> (often some kind of <a href="/wiki/Parse_tree" title="Parse tree" class="mw-redirect">parse tree</a>, <a href="/wiki/Abstract_syntax_tree" title="Abstract syntax tree">abstract syntax tree</a> or other hierarchical structure) implicit in the input tokens. The parser often uses a separate <a href="/wiki/Lexical_analysis" title="Lexical analysis">lexical analyser</a> to create tokens from the sequence of input characters. Parsers may be programmed by hand or may be (semi-)automatically generated (in some programming languages) by a tool (such as <a href="/wiki/Yet_Another_Compiler_Compiler" title="Yet Another Compiler Compiler" class="mw-redirect">Yacc</a>) from a grammar written in <a href="/wiki/Backus-Naur_form" title="Backus-Naur form" class="mw-redirect">Backus-Naur form</a>.</p> 
<h2><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=2" title="Edit section: Human languages">edit</a>]</span> <span class="mw-headline" id="Human_languages">Human languages</span></h2> 
<div class="rellink boilerplate seealso">See also: <a href="/wiki/Category:Natural_language_parsing" title="Category:Natural language parsing">Category:Natural language parsing</a></div> 
<p>In some <a href="/wiki/Machine_translation" title="Machine translation">machine translation</a> and <a href="/wiki/Natural_language_processing" title="Natural language processing">natural language processing</a> systems, human languages are parsed by computer programs. Human sentences are not easily parsed by programs, as there is substantial <a href="/wiki/Syntactic_ambiguity" title="Syntactic ambiguity">ambiguity</a> in the structure of human language, whose usage is to convey meaning (or <a href="/wiki/Semantics" title="Semantics">semantics</a>) amongst a potentially unlimited range of possibilities but only some of which are germane to the particular case. So an utterance "Man bites dog" versus "Dog bites man" is definite on one detail but in another language might appear as "Man dog is biting" with a reliance on the larger context to distinguish between those two possibilities, if indeed that difference was of concern. It is difficult to prepare formal rules to describe informal behaviour even though it is clear that some rules are being followed.</p> 
<p>In order to parse natural language data, researchers must first agree on the <a href="/wiki/Grammar" title="Grammar">grammar</a> to be used. The choice of syntax is affected by both <a href="/wiki/Language" title="Language">linguistic</a> and computational concerns; for instance some parsing systems use <a href="/wiki/Lexical_functional_grammar" title="Lexical functional grammar">lexical functional grammar</a>, but in general, parsing for grammars of this type is known to be <a href="/wiki/NP-complete" title="NP-complete">NP-complete</a>. <a href="/wiki/Head-driven_phrase_structure_grammar" title="Head-driven phrase structure grammar">Head-driven phrase structure grammar</a> is another linguistic formalism which has been popular in the parsing community, but other research efforts have focused on less complex formalisms such as the one used in the Penn <a href="/wiki/Treebank" title="Treebank">Treebank</a>. <a href="/wiki/Shallow_parsing" title="Shallow parsing">Shallow parsing</a> aims to find only the boundaries of major constituents such as noun phrases. Another popular strategy for avoiding linguistic controversy is <a href="/wiki/Dependency_grammar" title="Dependency grammar">dependency grammar</a> parsing.</p> 
<p>Most modern parsers are at least partly <a href="/wiki/Statistics" title="Statistics">statistical</a>; that is, they rely on a corpus of training data which has already been annotated (parsed by hand). This approach allows the system to gather information about the frequency with which various constructions occur in specific contexts. <i>(See <a href="/wiki/Machine_learning" title="Machine learning">machine learning</a>.)</i> Approaches which have been used include straightforward <a href="/wiki/PCFG" title="PCFG" class="mw-redirect">PCFGs</a> (probabilistic context free grammars), <a href="/wiki/Maximum_entropy" title="Maximum entropy">maximum entropy</a>, and <a href="/wiki/Neural_net" title="Neural net" class="mw-redirect">neural nets</a>. Most of the more successful systems use <i>lexical</i> statistics (that is, they consider the identities of the words involved, as well as their <a href="/wiki/Part_of_speech" title="Part of speech" class="mw-redirect">part of speech</a>). However such systems are vulnerable to <a href="/wiki/Overfitting" title="Overfitting">overfitting</a> and require some kind of smoothing to be effective.<sup class="noprint Template-Fact" title="This claim needs references to reliable sources from May 2008" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed">citation needed</a></i>]</sup></p> 
<p>Parsing algorithms for natural language cannot rely on the grammar having 'nice' properties as with manually-designed grammars for programming languages. As mentioned earlier some grammar formalisms are very difficult to parse computationally; in general, even if the desired structure is not <a href="/wiki/Context-free" title="Context-free" class="mw-redirect">context-free</a>, some kind of context-free approximation to the grammar is used to perform a first pass. Algorithms which use context-free grammars often rely on some variant of the <a href="/wiki/CKY_algorithm" title="CKY algorithm" class="mw-redirect">CKY algorithm</a>, usually with some <a href="/wiki/Heuristic_(computer_science)" title="Heuristic (computer science)" class="mw-redirect">heuristic</a> to prune away unlikely analyses to save time. <i>(See <a href="/wiki/Chart_parsing" title="Chart parsing" class="mw-redirect">chart parsing</a>.)</i> However some systems trade speed for accuracy using, eg, linear-time versions of the <a href="/wiki/Shift-reduce_parsing" title="Shift-reduce parsing" class="mw-redirect">shift-reduce</a> algorithm. A somewhat recent development has been <a href="/w/index.php?title=Parse_reranking&amp;action=edit&amp;redlink=1" class="new" title="Parse reranking (page does not exist)">parse reranking</a> in which the parser proposes some large number of analyses, and a more complex system selects the best option.</p> 
<h2><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=3" title="Edit section: Programming languages">edit</a>]</span> <span class="mw-headline" id="Programming_languages">Programming languages</span></h2> 
<p>The most common use of a parser is as a component of a <a href="/wiki/Compiler" title="Compiler">compiler</a> or <a href="/wiki/Interpreter" title="Interpreter" class="mw-redirect">interpreter</a>. This parses the <a href="/wiki/Source_code" title="Source code">source code</a> of a <a href="/wiki/Computer_programming_language" title="Computer programming language" class="mw-redirect">computer programming language</a> to create some form of internal representation. Programming languages tend to be specified in terms of a <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a> because fast and efficient parsers can be written for them. Parsers are written by hand or generated by <a href="/wiki/Parser_generator" title="Parser generator" class="mw-redirect">parser generators</a>.</p> 
<p>Context-free grammars are limited in the extent to which they can express all of the requirements of a language. Informally, the reason is that the memory of such a language is limited. The grammar cannot remember the presence of a construct over an arbitrarily long input; this is necessary for a language in which, for example, a name must be declared before it may be referenced. More powerful grammars that can express this constraint, however, cannot be parsed efficiently. Thus, it is a common strategy to create a relaxed parser for a context-free grammar which accepts a superset of the desired language constructs (that is, it accepts some invalid constructs); later, the unwanted constructs can be filtered out.</p> 
<h3><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=4" title="Edit section: Overview of process">edit</a>]</span> <span class="mw-headline" id="Overview_of_process">Overview of process</span></h3> 
<div class="floatright"><a href="/wiki/File:Parser_Flow.gif" class="image" title="Flow of data in a typical parser"><img alt="Flow of data in a typical parser" src="http://upload.wikimedia.org/wikipedia/en/a/a9/Parser_Flow.gif" width="147" height="409" /></a></div> 
<p>The following example demonstrates the common case of parsing a computer language with two levels of grammar: lexical and syntactic.</p> 
<p>The first stage is the token generation, or <a href="/wiki/Lexical_analysis" title="Lexical analysis">lexical analysis</a>, by which the input character stream is split into meaningful symbols defined by a grammar of <a href="/wiki/Regular_expression" title="Regular expression">regular expressions</a>. For example, a calculator program would look at an input such as "<code>12*(3+4)^2</code>" and split it into the tokens <code>12</code>, <code>*</code>, <code>(</code>, <code>3</code>, <code>+</code>, <code>4</code>, <code>)</code>, <code>^</code>, and <code>2</code>, each of which is a meaningful symbol in the context of an arithmetic expression. The lexer would contain rules to tell it that the characters <code>*</code>, <code>+</code>, <code>^</code>, <code>(</code> and <code>)</code> mark the start of a new token, so meaningless tokens like "<code>12*</code>" or "<code>(3</code>" will not be generated.</p> 
<p>The next stage is parsing or <a href="/wiki/Syntactic_analysis" title="Syntactic analysis" class="mw-redirect">syntactic analysis</a>, which is checking that the tokens form an allowable expression. This is usually done with reference to a <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a> which recursively defines components that can make up an expression and the order in which they must appear. However, not all rules defining programming languages can be expressed by context-free grammars alone, for example type validity and proper declaration of identifiers. These rules can be formally expressed with <a href="/wiki/Attribute_grammar" title="Attribute grammar">attribute grammars</a>.</p> 
<p>The final phase is <a href="/wiki/Semantic_analysis_(computer_science)" title="Semantic analysis (computer science)" class="mw-redirect">semantic parsing</a> or analysis, which is working out the implications of the expression just validated and taking the appropriate action. In the case of a calculator or interpreter, the action is to evaluate the expression or program; a compiler, on the other hand, would generate some kind of code. Attribute grammars can also be used to define these actions.</p> 
<h2><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=5" title="Edit section: Types of parser">edit</a>]</span> <span class="mw-headline" id="Types_of_parser">Types of parser</span></h2> 
<p>The task of the parser is essentially to determine if and how the input can be derived from the start symbol of the grammar. This can be done in essentially two ways:</p> 
<ul> 
<li><a href="/wiki/Top-down_parsing" title="Top-down parsing">Top-down parsing</a>- Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for <a href="/wiki/Parse_tree" title="Parse tree" class="mw-redirect">parse trees</a> using a top-down expansion of the given <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a> rules. Tokens are consumed from left to right. Inclusive choice is used to accommodate <a href="/wiki/Ambiguity" title="Ambiguity">ambiguity</a> by expanding all alternative right-hand-sides of grammar rules.<sup id="cite_ref-AhoSethiUllman_1986_2-0" class="reference"><a href="#cite_note-AhoSethiUllman_1986-2"><span>[</span>3<span>]</span></a></sup></li> 
<li><a href="/wiki/Bottom-up_parsing" title="Bottom-up parsing">Bottom-up parsing</a> - A parser can start with the input and attempt to rewrite it to the start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on. <a href="/wiki/LR_parser" title="LR parser">LR parsers</a> are examples of bottom-up parsers. Another term used for this type of parser is Shift-Reduce parsing.</li> 
</ul> 
<p><a href="/wiki/LL_parser" title="LL parser">LL parsers</a> and <a href="/wiki/Recursive-descent_parser" title="Recursive-descent parser" class="mw-redirect">recursive-descent parser</a> are examples of top-down parsers which cannot accommodate <a href="/wiki/Left_recursion" title="Left recursion">left recursive</a> productions. Although it has been believed that simple implementations of top-down parsing cannot accommodate direct and indirect left-recursion and may require exponential time and space complexity while parsing ambiguous <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammars</a>, more sophisticated algorithms for top-down parsing have been created by Frost, Hafiz, and Callaghan<sup id="cite_ref-FrostHafizCallaghan_2007_3-0" class="reference"><a href="#cite_note-FrostHafizCallaghan_2007-3"><span>[</span>4<span>]</span></a></sup><sup id="cite_ref-FrostHafizCallaghan_2008_4-0" class="reference"><a href="#cite_note-FrostHafizCallaghan_2008-4"><span>[</span>5<span>]</span></a></sup> which accommodate <a href="/wiki/Ambiguity" title="Ambiguity">ambiguity</a> and <a href="/wiki/Left_recursion" title="Left recursion">left recursion</a> in polynomial time and which generates polynomial-size representations of the potentially-exponential number of parse trees. Their algorithm is able to produce both left-most and right-most derivations of an input with regard to a given <a href="/wiki/Context-free_grammar" title="Context-free grammar">CFG</a>.</p> 
<p>An important distinction with regard to parsers is whether a parser generates a <i>leftmost derivation</i> or a <i>rightmost derivation</i> (see <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a>). LL parsers will generate a leftmost <a href="/wiki/Derivation" title="Derivation">derivation</a> and LR parsers will generate a rightmost derivation (although usually in reverse).<sup class="noprint Template-Fact" title="This claim needs references to reliable sources from January 2008" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed">citation needed</a></i>]</sup></p> 
<h2><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=6" title="Edit section: Examples of parsers">edit</a>]</span> <span class="mw-headline" id="Examples_of_parsers">Examples of parsers</span></h2> 
<h3><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=7" title="Edit section: Top-down parsers">edit</a>]</span> <span class="mw-headline" id="Top-down_parsers">Top-down parsers</span></h3> 
<p>Some of the parsers that use <a href="/wiki/Top-down_parsing" title="Top-down parsing">top-down parsing</a> include:</p> 
<ul> 
<li><a href="/wiki/Recursive_descent_parser" title="Recursive descent parser">Recursive descent parser</a></li> 
<li><a href="/wiki/LL_parser" title="LL parser">LL parser</a> (<b>L</b>eft-to-right, <b>L</b>eftmost derivation)</li> 
<li><a href="http://www.cs.uwindsor.ca/~hafiz/proHome.html" class="external text" rel="nofollow">X-SAIGA</a> - eXecutable SpecificAtIons of GrAmmars. Contains publications related to top-down parsing algorithm that supports left-recursion and ambiguity in polynomial time and space.</li> 
</ul> 
<h3><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=8" title="Edit section: Bottom-up parsers">edit</a>]</span> <span class="mw-headline" id="Bottom-up_parsers">Bottom-up parsers</span></h3> 
<p>Some of the parsers that use <a href="/wiki/Bottom-up_parsing" title="Bottom-up parsing">bottom-up parsing</a> include:</p> 
<ul> 
<li>Precedence parser
<ul> 
<li><a href="/wiki/Operator-precedence_parser" title="Operator-precedence parser">Operator-precedence parser</a></li> 
<li><a href="/wiki/Simple_precedence_parser" title="Simple precedence parser">Simple precedence parser</a></li> 
</ul> 
</li> 
<li>BC (bounded context) parsing</li> 
<li><a href="/wiki/LR_parser" title="LR parser">LR parser</a> (<b>L</b>eft-to-right, <b>R</b>ightmost derivation)
<ul> 
<li><a href="/wiki/SLR_parser" title="SLR parser" class="mw-redirect">Simple LR (SLR) parser</a></li> 
<li><a href="/wiki/LALR_parser" title="LALR parser">LALR parser</a></li> 
<li><a href="/wiki/Canonical_LR_parser" title="Canonical LR parser">Canonical LR (LR(1)) parser</a></li> 
<li><a href="/wiki/GLR_parser" title="GLR parser">GLR parser</a></li> 
</ul> 
</li> 
<li><a href="/wiki/CYK_algorithm" title="CYK algorithm">CYK parser</a></li> 
</ul> 
<h3><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=9" title="Edit section: Parser development software">edit</a>]</span> <span class="mw-headline" id="Parser_development_software">Parser development software</span></h3> 
<p>Some of the well known parser development tools include the following. Also see <a href="/wiki/Comparison_of_parser_generators" title="Comparison of parser generators">comparison of parser generators</a>.</p> 
<div style="-moz-column-count:3; column-count:3;"> 
<ul> 
<li><a href="/wiki/ANTLR" title="ANTLR">ANTLR</a></li> 
<li><a href="/wiki/GNU_bison" title="GNU bison">Bison</a></li> 
<li><a href="/wiki/Coco/R" title="Coco/R">Coco/R</a></li> 
<li><a href="/wiki/GOLD_(parser)" title="GOLD (parser)">GOLD</a></li> 
<li><a href="/wiki/JavaCC" title="JavaCC">JavaCC</a></li> 
<li><a href="/wiki/Lex_programming_tool" title="Lex programming tool" class="mw-redirect">Lex</a></li> 
<li><a href="/wiki/Ragel" title="Ragel">Ragel</a></li> 
<li><a href="/wiki/Syntax_Definition_Formalism" title="Syntax Definition Formalism">Syntax Definition Formalism</a></li> 
<li><a href="/wiki/Spirit_Parser_Framework" title="Spirit Parser Framework">Spirit Parser Framework</a></li> 
<li><a href="/wiki/SYNTAX" title="SYNTAX">SYNTAX</a></li> 
<li><a href="/wiki/Yacc" title="Yacc">Yacc</a></li> 
<li><a href="/wiki/Lemon_Parser" title="Lemon Parser" class="mw-redirect">Lemon</a></li> 
</ul> 
</div> 
<h2><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=10" title="Edit section: See also">edit</a>]</span> <span class="mw-headline" id="See_also">See also</span></h2> 
<ul> 
<li><a href="/wiki/Generating_strings" title="Generating strings">Generating strings</a></li> 
<li><a href="/wiki/Grammar_checker" title="Grammar checker">Grammar checker</a></li> 
<li><a href="/wiki/Chart_parser" title="Chart parser">Chart parser</a></li> 
<li><a href="/wiki/Compiler-compiler" title="Compiler-compiler">Compiler-compiler</a></li> 
<li><a href="/wiki/Deterministic_parsing" title="Deterministic parsing">Deterministic parsing</a></li> 
<li><a href="/wiki/Lexing" title="Lexing" class="mw-redirect">Lexing</a></li> 
<li><a href="/wiki/Shallow_parsing" title="Shallow parsing">Shallow parsing</a></li> 
</ul> 
<h2><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=11" title="Edit section: References">edit</a>]</span> <span class="mw-headline" id="References">References</span></h2> 
<div class="references-small"> 
<ol class="references"> 
<li id="cite_note-0"><b><a href="#cite_ref-0">^</a></b> <a href="http://www.bartleby.com/61/33/P0083300.html" class="external free" rel="nofollow">http://www.bartleby.com/61/33/P0083300.html</a></li> 
<li id="cite_note-1"><b><a href="#cite_ref-1">^</a></b> <a href="http://dictionary.reference.com/search?q=parse&amp;x=0&amp;y=0" class="external free" rel="nofollow">http://dictionary.reference.com/search?q=parse&amp;x=0&amp;y=0</a></li> 
<li id="cite_note-AhoSethiUllman_1986-2"><b><a href="#cite_ref-AhoSethiUllman_1986_2-0">^</a></b> Aho, A.V., Sethi, R. and Ullman ,J.D. (1986) " Compilers: principles, techniques, and tools." <i>Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.</i></li> 
<li id="cite_note-FrostHafizCallaghan_2007-3"><b><a href="#cite_ref-FrostHafizCallaghan_2007_3-0">^</a></b> Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ." <i>10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE</i> , Pages: 109 - 120, June 2007, Prague.</li> 
<li id="cite_note-FrostHafizCallaghan_2008-4"><b><a href="#cite_ref-FrostHafizCallaghan_2008_4-0">^</a></b> Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." <i>10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN</i> , Volume 4902/2008, Pages: 167 - 181, January 2008, San Francisco.</li> 
</ol> 
</div> 
<h2><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=12" title="Edit section: Further reading">edit</a>]</span> <span class="mw-headline" id="Further_reading">Further reading</span></h2> 
<ul> 
<li>Chapman, Nigel P., <a href="http://books.google.com/books?id=nEA9AAAAIAAJ&amp;printsec=frontcover" class="external text" rel="nofollow"><i>LR Parsing: Theory and Practice</i></a>, Cambridge University Press, 1987. <a href="/wiki/Special:BookSources/052130413X" class="internal mw-magiclink-isbn">ISBN 052130413X</a></li> 
<li>Grune, Dick; Jacobs, Ceriel J.H., <a href="http://www.cs.vu.nl/~dick/PTAPG.html" class="external text" rel="nofollow"><i>Parsing Techniques - A Practical Guide</i></a>, VU University Amsterdam, Amsterdam, The Netherlands. Originally published by Ellis Horwood, Chichester, England, 1990; <a href="/wiki/Special:BookSources/0136514316" class="internal mw-magiclink-isbn">ISBN 0136514316</a></li> 
</ul> 
<h2><span class="editsection">[<a href="/w/index.php?title=Parsing&amp;action=edit&amp;section=13" title="Edit section: External links">edit</a>]</span> <span class="mw-headline" id="External_links">External links</span></h2> 
<ul> 
<li><a href="http://code.google.com/p/nobjectiveast/" class="external text" rel="nofollow">Objective-C parser written in C#</a></li> 
<li><a href="http://www.hwaci.com/sw/lemon/" class="external text" rel="nofollow">The Lemon LALR Parser Generator</a></li> 
</ul> 
 
 
<!-- 
NewPP limit report
Preprocessor node count: 796/1000000
Post-expand include size: 9320/2048000 bytes
Template argument size: 3422/2048000 bytes
Expensive parser function count: 3/500
--> 
 
<!-- Saved in parser cache with key enwiki:pcache:idhash:310015-0!1!0!default!!en!2 and timestamp 20100111015715 --> 
<div class="printfooter"> 
Retrieved from "<a href="http://en.wikipedia.org/wiki/Parsing">http://en.wikipedia.org/wiki/Parsing</a>"</div> 
            <div id='catlinks' class='catlinks'><div id="mw-normal-catlinks"><a href="/wiki/Special:Categories" title="Special:Categories">Categories</a>: <span dir='ltr'><a href="/wiki/Category:Algorithms_on_strings" title="Category:Algorithms on strings">Algorithms on strings</a></span> | <span dir='ltr'><a href="/wiki/Category:Compiler_theory" title="Category:Compiler theory">Compiler theory</a></span> | <span dir='ltr'><a href="/wiki/Category:Parsing" title="Category:Parsing">Parsing</a></span></div><div id="mw-hidden-catlinks" class="mw-hidden-cats-hidden">Hidden categories: <span dir='ltr'><a href="/wiki/Category:Articles_needing_additional_references_from_August_2008" title="Category:Articles needing additional references from August 2008">Articles needing additional references from August 2008</a></span> | <span dir='ltr'><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></span> | <span dir='ltr'><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></span> | <span dir='ltr'><a href="/wiki/Category:Articles_with_unsourced_statements_from_May_2008" title="Category:Articles with unsourced statements from May 2008">Articles with unsourced statements from May 2008</a></span> | <span dir='ltr'><a href="/wiki/Category:Articles_with_unsourced_statements_from_January_2008" title="Category:Articles with unsourced statements from January 2008">Articles with unsourced statements from January 2008</a></span></div></div>         <!-- end content --> 
                        <div class="visualClear"></div> 
        </div> 
    </div> 
        </div> 
        <div id="column-one"> 
    <div id="p-cactions" class="portlet"> 
        <h5>Views</h5> 
        <div class="pBody"> 
            <ul lang="en" xml:lang="en"> 
    
                 <li id="ca-nstab-main" class="selected"><a href="/wiki/Parsing" title="View the content page [c]" accesskey="c">Article</a></li> 
                 <li id="ca-talk"><a href="/wiki/Talk:Parsing" title="Discussion about the content page [t]" accesskey="t">Discussion</a></li> 
                 <li id="ca-edit"><a href="/w/index.php?title=Parsing&amp;action=edit" title="You can edit this page. &#10;Please use the preview button before saving. [e]" accesskey="e">Edit this page</a></li> 
                 <li id="ca-history"><a href="/w/index.php?title=Parsing&amp;action=history" title="Past versions of this page [h]" accesskey="h">History</a></li>          </ul> 
        </div> 
    </div> 
    <div class="portlet" id="p-personal"> 
        <h5>Personal tools</h5> 
        <div class="pBody"> 
            <ul lang="en" xml:lang="en"> 
                <li id="pt-optin-try"><a href="http://en.wikipedia.org/w/index.php?title=Special:UsabilityInitiativeOptIn&amp;from=Parsing" title="Try out new features" class="no-text-transform">Try Beta</a></li> 
                <li id="pt-login"><a href="/w/index.php?title=Special:UserLogin&amp;returnto=Parsing" title="You are encouraged to log in; however, it is not mandatory. [o]" accesskey="o">Log in / create account</a></li> 
            </ul> 
        </div> 
    </div> 
    <div class="portlet" id="p-logo"> 
        <a style="background-image: url(http://upload.wikimedia.org/wikipedia/en/b/bc/Wiki.png);" href="/wiki/Main_Page" title="Visit the main page"></a> 
    </div> 
    <script type="text/javascript"> if (window.isMSIE55) fixalpha(); </script> 
    <div class='generated-sidebar portlet' id='p-navigation'> 
        <h5 lang="en" xml:lang="en">Navigation</h5> 
        <div class='pBody'> 
            <ul> 
                <li id="n-mainpage-description"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z">Main page</a></li> 
                <li id="n-contents"><a href="/wiki/Portal:Contents" title="Guides to browsing Wikipedia">Contents</a></li> 
                <li id="n-featuredcontent"><a href="/wiki/Portal:Featured_content" title="Featured content — the best of Wikipedia">Featured content</a></li> 
                <li id="n-currentevents"><a href="/wiki/Portal:Current_events" title="Find background information on current events">Current events</a></li> 
                <li id="n-randompage"><a href="/wiki/Special:Random" title="Load a random article [x]" accesskey="x">Random article</a></li> 
            </ul> 
        </div> 
    </div> 
    <div id="p-search" class="portlet"> 
        <h5 lang="en" xml:lang="en"><label for="searchInput">Search</label></h5> 
        <div id="searchBody" class="pBody"> 
            <form action="/w/index.php" id="searchform"> 
                <input type='hidden' name="title" value="Special:Search"/> 
                <input id="searchInput" title="Search Wikipedia" accesskey="f" value="" name="search" /> 
                <input type='submit' name="go" class="searchButton" id="searchGoButton" value="Go" title="Go to a page with this exact name if one exists" />&nbsp;
                <input type='submit' name="fulltext" class="searchButton" id="mw-searchButton" value="Search" title="Search Wikipedia for this text" /> 
            </form> 
        </div> 
    </div> 
    <div class='generated-sidebar portlet' id='p-interaction'> 
        <h5 lang="en" xml:lang="en">Interaction</h5> 
        <div class='pBody'> 
            <ul> 
                <li id="n-aboutsite"><a href="/wiki/Wikipedia:About" title="Find out about Wikipedia">About Wikipedia</a></li> 
                <li id="n-portal"><a href="/wiki/Wikipedia:Community_portal" title="About the project, what you can do, where to find things">Community portal</a></li> 
                <li id="n-recentchanges"><a href="/wiki/Special:RecentChanges" title="The list of recent changes in the wiki [r]" accesskey="r">Recent changes</a></li> 
                <li id="n-contact"><a href="/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia">Contact Wikipedia</a></li> 
                <li id="n-sitesupport"><a href="http://wikimediafoundation.org/wiki/Support_Wikipedia/en" title="Support us">Donate to Wikipedia</a></li> 
                <li id="n-help"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia">Help</a></li> 
            </ul> 
        </div> 
    </div> 
    <div class="portlet" id="p-tb"> 
        <h5 lang="en" xml:lang="en">Toolbox</h5> 
        <div class="pBody"> 
            <ul> 
                <li id="t-whatlinkshere"><a href="/wiki/Special:WhatLinksHere/Parsing" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j">What links here</a></li> 
                <li id="t-recentchangeslinked"><a href="/wiki/Special:RecentChangesLinked/Parsing" title="Recent changes in pages linked from this page [k]" accesskey="k">Related changes</a></li> 
<li id="t-upload"><a href="/wiki/Wikipedia:Upload" title="Upload files [u]" accesskey="u">Upload file</a></li> 
<li id="t-specialpages"><a href="/wiki/Special:SpecialPages" title="List of all special pages [q]" accesskey="q">Special pages</a></li> 
                <li id="t-print"><a href="/w/index.php?title=Parsing&amp;printable=yes" rel="alternate" title="Printable version of this page [p]" accesskey="p">Printable version</a></li>             <li id="t-permalink"><a href="/w/index.php?title=Parsing&amp;oldid=333278307" title="Permanent link to this revision of the page">Permanent link</a></li><li id="t-cite"><a href="/w/index.php?title=Special:Cite&amp;page=Parsing&amp;id=333278307" title="Information on how to cite this page">Cite this page</a></li>           </ul> 
        </div> 
    </div> 
    <div id="p-lang" class="portlet"> 
        <h5 lang="en" xml:lang="en">Languages</h5> 
        <div class="pBody"> 
            <ul> 
                <li class="interwiki-ca"><a href="http://ca.wikipedia.org/wiki/Analitzador_sint%C3%A0ctic">Català</a></li> 
                <li class="interwiki-cs"><a href="http://cs.wikipedia.org/wiki/Syntaktick%C3%A1_anal%C3%BDza">Česky</a></li> 
                <li class="interwiki-de"><a href="http://de.wikipedia.org/wiki/Parser">Deutsch</a></li> 
                <li class="interwiki-es"><a href="http://es.wikipedia.org/wiki/Analizador_sint%C3%A1ctico">Español</a></li> 
                <li class="interwiki-fa"><a href="http://fa.wikipedia.org/wiki/%D8%AA%D8%AC%D8%B2%DB%8C%D9%87_%DA%A9%D9%86%D9%86%D8%AF%D9%87">فارسی</a></li> 
                <li class="interwiki-fr"><a href="http://fr.wikipedia.org/wiki/D%C3%A9composition_analytique">Français</a></li> 
                <li class="interwiki-ko"><a href="http://ko.wikipedia.org/wiki/%EA%B5%AC%EB%AC%B8_%EB%B6%84%EC%84%9D">한국어</a></li> 
                <li class="interwiki-hr"><a href="http://hr.wikipedia.org/wiki/Parsiranje">Hrvatski</a></li> 
                <li class="interwiki-id"><a href="http://id.wikipedia.org/wiki/Parsing">Bahasa Indonesia</a></li> 
                <li class="interwiki-it"><a href="http://it.wikipedia.org/wiki/Parsing">Italiano</a></li> 
                <li class="interwiki-hu"><a href="http://hu.wikipedia.org/wiki/Elemz%C5%91_(informatika)">Magyar</a></li> 
                <li class="interwiki-mk"><a href="http://mk.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D1%81%D0%B5%D1%80">Македонски</a></li> 
                <li class="interwiki-nl"><a href="http://nl.wikipedia.org/wiki/Parser">Nederlands</a></li> 
                <li class="interwiki-ja"><a href="http://ja.wikipedia.org/wiki/%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90">日本語</a></li> 
                <li class="interwiki-pl"><a href="http://pl.wikipedia.org/wiki/Parser">Polski</a></li> 
                <li class="interwiki-pt"><a href="http://pt.wikipedia.org/wiki/An%C3%A1lise_sint%C3%A1tica_(computa%C3%A7%C3%A3o)">Português</a></li> 
                <li class="interwiki-ro"><a href="http://ro.wikipedia.org/wiki/Parsare">Română</a></li> 
                <li class="interwiki-ru"><a href="http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D1%82%D0%B0%D0%BA%D1%81%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7">Русский</a></li> 
                <li class="interwiki-sr"><a href="http://sr.wikipedia.org/wiki/Parsiranje">Српски / Srpski</a></li> 
                <li class="interwiki-fi"><a href="http://fi.wikipedia.org/wiki/J%C3%A4sennin">Suomi</a></li> 
                <li class="interwiki-sv"><a href="http://sv.wikipedia.org/wiki/Parser">Svenska</a></li> 
            </ul> 
        </div> 
    </div> 
        </div><!-- end of the left (by default at least) column --> 
            <div class="visualClear"></div> 
            <div id="footer"> 
                <div id="f-poweredbyico"><a href="http://www.mediawiki.org/"><img src="http://bits.wikimedia.org/skins-1.5/common/images/poweredby_mediawiki_88x31.png" height="31" width="88" alt="Powered by MediaWiki" /></a></div> 
                <div id="f-copyrightico"><a href="http://wikimediafoundation.org/"><img src="/images/wikimedia-button.png" width="88" height="31" alt="Wikimedia Foundation"/></a></div> 
            <ul id="f-list"> 
                    <li id="lastmod"> This page was last modified on 22 December 2009 at 15:27.</li> 
                    <li id="copyright">Text is available under the <a rel="license" href="http://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License">Creative Commons Attribution-ShareAlike License</a><a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/" style="display:none;"></a>;
additional terms may apply.
See <a href="http://wikimediafoundation.org/wiki/Terms_of_Use">Terms of Use</a> for details.<br/> 
Wikipedia&reg; is a registered trademark of the <a href="http://www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li><li><a class='internal' href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact us</a></li> 
                    <li id="privacy"><a href="http://wikimediafoundation.org/wiki/Privacy_policy" title="wikimedia:Privacy policy">Privacy policy</a></li> 
                    <li id="about"><a href="/wiki/Wikipedia:About" title="Wikipedia:About">About Wikipedia</a></li> 
                    <li id="disclaimer"><a href="/wiki/Wikipedia:General_disclaimer" title="Wikipedia:General disclaimer">Disclaimers</a></li> 
            </ul> 
        </div> 
</div> 
 
<script type="text/javascript">if (window.runOnloadHook) runOnloadHook();</script> 
<!-- Served by srv190 in 0.042 secs. --></body></html> 